package leecode;


import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Stack;

/**
 * @author: lwg
 * @Date: 2021/5/4 16:22
 * @Description: 前k个最小的数
 */
public class demo40 {

    /**
     * 方法1.利用堆排序的方法进行实现
     */
    /*public static int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0) {
            //当k=0时,我们需要返回数组中的第一个数满足题目的要求
            return new int[0];
        }
        //堆排序默认小顶堆，利用compare变换成大顶堆
        Queue<Integer> heap = new PriorityQueue<>(k, (i1, i2) -> Integer.compare(i2, i1));
        //遍历放入的元素
        for (int e : arr) {
            //当堆为空或者堆内长度小于设定的k时或者放入的元素小于堆顶元素时
            if (heap.isEmpty() || heap.size() <= k || e < heap.peek()) {
                heap.offer(e);
            }
            //当堆中的元素超过k个时，移除堆顶元素
            if (heap.size() > k) {
                heap.poll();
            }
        }

        //将堆中的元素存入新的数组中
        int[] res=new int[heap.size()];
        int j=0;
        for (Integer e : heap) {
            res[j++]=e;
        }
        return res;

    }
*/

    /**
     * 方法2：快速选择
     */
    public static int[] getLeastNumbers(int[] arr, int k) {
        //如果k>数组的长度直接返回整个数组
        if (k > arr.length) {
            return arr;
        }
        return quickSort(arr, k, 0, arr.length - 1);
       
    }

    private static int[] quickSort(int[] arr, int k, int l, int r) {
        int i = l;
        int j = r;
        while (i < j) {
            while (i < j && arr[j] >= arr[l]) {
                j--;
            }
            while (i < j && arr[i] <= arr[l]) {
                i++;
            }
            swap(arr, i, j);
        }
        swap(arr, i, l);
        //如果要查找的数的范围小于基准数所在的数组下标，则要查找的数在基准数的左边
        if (k < i) {
            return quickSort(arr, k, l, i - 1);
        }
        if (k > i) {
            return quickSort(arr, k, i + 1, r);
        }
        return Arrays.copyOf(arr, k);
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }


    public static void main(String[] args) {
        int[] array = new int[]{5, 4, 6, 3, 4, 8, 6, 4, 2, 5, 1, 3};
        System.out.println(Arrays.toString(getLeastNumbers(array, 5)));
    }
}
